#include "Format.h"

class MergeSort {
public:
    MergeSort();

   MergeSort(int *arr, int num) {
        MergeSort();
        this->sort(arr, num);
        Format::format(arr, num);
    }
    ~MergeSort();

private:
    void sort(int *arr, int num);
    void Merge(int *arr, int a, int b, int length, int n, int *temp);
};

MergeSort::MergeSort() {

}

MergeSort::~MergeSort() {

}

void MergeSort::Merge(int *arr, int a, int b, int length, int n, int *temp) {
    int compareCount = 0, moveCount = 0;
    int right;
    if (b + length - 1 >= n - 1) {
        right = n - b;
        moveCount++;
    } else {
        right = length;
        moveCount++;
    }
    compareCount++;
    int i = 0, j = 0;
    moveCount += 2;
    while (i <= length - 1 && j <= right - 1) {
        if (arr[a + i] <= arr[b + j]) {
            temp[i + j] = arr[a + i];
            i++;
            moveCount += 2;
        } else {
            temp[i + j] = arr[b + j];
            j++;
            moveCount += 2;
        }
        moveCount++;
        compareCount += 2;
    }
    if (j == right) {//a�л���Ԫ�أ���ȫ����b�еĴ�,a[i]��δʹ��
        // memcpy(arr + a + i + j, arr + a + i, (length - i) * sizeof (int));
        for (int k = 0; k < length - i; k++) {
            arr[a + i + j + k] = arr[a + i + k];
        }
    }
    compareCount++;
    moveCount = moveCount + length - i;
    // memcpy(arr + a, temp, (i + j) * sizeof (int));
    for (int k = 0; k < i + j; k++) {
        arr[a + k] = temp[k];
    }
    moveCount = moveCount + i + j;
    arr[TestNumber] += moveCount;
    arr[TestNumber + 1] += compareCount;

}

void MergeSort::sort(int *arr, int n) {
    int compareCount = 0, moveCount = 0;
    int step = 1;
    int* temp = new int[n];
    while (step < n) {
        for (int i = 0; i <= n - step - 1; i += 2 * step) {
            Merge(arr, i, i + step, step, n, temp);
            compareCount++;
            moveCount++;
        }
        //��i��i+step�������������н��кϲ�
        //���г���Ϊstep
        //��i�Ժ�ĳ���С�ڻ��ߵ���stepʱ���˳�
        step *= 2; //�ڰ�ĳһ�����鲢����֮�󣬲����ӱ�
        compareCount++;
        moveCount++;
    }
    delete temp;
    arr[TestNumber] += moveCount;
    arr[TestNumber + 1] += compareCount;
}